Parallel computer systems have proven to be an expedient solution for achieving greatly increased processing speeds heretofore beyond the capabilities of conventional computational architectures. With the advent of massively parallel processing machines such as the IBM RS/6000 SP1 and the IBM RS/6000 SP2, volumes of data may be efficiently managed and complex computations may be rapidly performed. (IBM and RS/6000 are registered trademarks of International Business Machines Corporation, Old Orchard Road, Armonk, N.Y., the assignee of the present application.)
A typical massively parallel processing system may include a relatively large number, often in the hundreds or even thousands of separate, though relatively simple, microprocessor-based nodes which are interconnected via a communications fabric comprising a high speed packet switch network. Messages in the form of packets are routed over the network between the nodes enabling communication therebetween. As one example, a node may comprise a microprocessor and associated support circuitry such as random access memory (RAM), read only memory (ROM), and input/output (I/O) circuitry which may further include a communications subsystem having an interface for enabling the node to communicate through the network.
Among the wide variety of available forms of packet networks currently available, perhaps the most traditional architecture implements a multi-stage interconnected arrangement of relatively small cross point switches, with each switch typically being an N-port bi-directional router where N is usually either 4 or 8, with each of the N ports internally interconnected via a cross point matrix. For purposes herein, the switch may be considered an 8 port router switch. In such a network, each switch in one stage, beginning at one side (so-called input side) of the network is interconnected through a unique path (typically a byte-wide physical connection) to a switch in the next succeeding stage, and so forth until the last stage is reached at an opposite side (so called output side) of the network. The bi-directional router switch included in this network is generally available as a single integrated circuit (i.e., a “switch chip”) which is operationally non-blocking, and accordingly a popular design choice. Such a switch chip is described in U.S. Pat. No. 5,546,391 entitled “A Central Shared Queue Based Time Multiplexed Packet Switch With Deadlock Avoidance” by P. Hochschild et al., issued on Aug. 31, 1996.
A switching network typically comprises a number of these switch chips organized into two interconnected stages, for example; a four switch chip input stage followed by a four switch chip output stage, all of the eight switch chips being included on a single switch board. With such an arrangement, messages passing between any two ports on different switch chips in the input stage would first be routed through the switch chip in the input stage that contains the source or input port, to any of the four switches comprising the output stage and subsequently, through the switch chip in the output stage the message would be routed back (i.e., the message packet would reverse its direction) to the switch chip in the input stage including the destination (output) port for the message. Alternatively, in larger systems comprising a plurality of such switch boards, messages may be routed from a processing node, through a switch chip in the input stage of the switch board to a switch chip in the output stage of the switch board and from the output stage switch chip to another interconnected switch board (and thereon to a switch chip in the input stage). Within an exemplary switch board, switch chips that are directly linked to nodes are termed node switch chips (NSCs) and those which are connected directly to other switch boards are termed link switch chips (LSCs).
Switch boards of the type described above may simply interconnect a plurality of nodes, or alternatively, in larger systems, a plurality of interconnected switch boards may have their input stages connected to nodes and their output stages connected to other switch boards, these are termed node switch boards (NSBs). Even more complex switching networks may comprise intermediate stage switch boards which are interposed between and interconnect a plurality of NSBs. These intermediate switch boards (ISBs) serve as a conduit for routing message packets between nodes coupled to switches in a first and a second NSB.
Switching networks are described further in U.S. Pat. Nos.: 6,021,442; 5,884,090; 5,812,549; 5,453,978; and 5,355,364, each of which is hereby incorporated herein by reference in its entirety.
One consideration in the operation of any switching network is that routes used to move messages should be selected such that a desired bandwidth is available for communication. One cause of loss of bandwidth is unbalanced distribution of routes between source-destination pairs and contention therebetween. While it is not possible to avoid contention for all traffic patterns, reduction of contention should be a goal. This goal can be partially achieved through generation of a globally balanced set of routes. The complexity of route generation depends on the type and size of the network as well as the number of routes used between any source-destination pair. Various techniques have been used for generating routes in a multi-path network. While some techniques generate routes dynamically, others generate static routes based on the connectivity of the network. Dynamic methods are often self-adjusting to variations in traffic patterns and tend to achieve as even a flow of traffic as possible. Static methods, on the other hand, are pre-computed and do not change during the normal operation of the network.
While pre-computing routing appears to be simpler, the burden of generating an acceptable set of routes that will be optimal for a variety of traffic patterns lies heavily on the algorithm that is used. Typically, global balancing of routes is addressed by these algorithms, while the issue of local balancing is overlooked, for example, because of the complexity involved.
Thus, a need remains in the art for a route generation technique that generates routes that are balanced both globally and locally in switching networks which support multiple paths between source-destination pairs.